“Let what you say be simply ‘Yes’ or ‘No’; anything more than this comes from evil.” - Matthew 5:37 (ESV)
Historically, the study of computability predates computers themselves! Long before the first computer was constructed, mathematicians and logicians were already thinking about what (mathematical) problems could be solved by humans, and what procedures they could use to do so.
In modern Computer Science, Computability is the study of what problems can and cannot be solved using computers. For this course, two points immediately arise:
Of course, if we want to rigorously prove which problems can or cannot be solved using computers, we need to define our terms:
Only then can we precisely characterize the solvable and unsolvable problems.
There are a huge number of different tasks we ask computers to do (play games, calculate physics simulations, edit documents, etc.) with more being added every day. Instead of trying to capture all this variety directly, we will make two simplifying assumptions that allow us to restrict our attention to what are called Decision Problems, since these allow very simple but precise mathematical descriptions. We will then argue that all real-world computations can be described as combinations of decision problems, so understanding which decision problems can be solved tells us which real-world computations can be performed.
"3 * 7""3 × 7""Hey Siri, what is three times seven?".mpg sound file
containing a human voice saying that previous sentence with a dog
barking in the background.)A problem where both those assumptions are true is called a decision problem. Examples of decision problems include:
"37".
Sample output: true.)"3×7=21". Sample output: true.)"sort([3,1,4,5,2]) = [1,2,3,4]". Sample output:
false)The first assumption, that the input is a finite string of characters from a finite alphabet, is just a generalization of principle that any sort of data (that we might want to operate on using a computer) can be encoded as 0’s and 1’s (binary). We could study all of computability requiring that all decision problems take sequences of bits as input, but it’s often convenient to imagine inputs containing more familiar characters (e.g., from ASCII or Unicode). Besides, historically not all computers have used a binary representation of data, and we don’t want to prematurely limit ourselves to considering only problems solvable by the current generation of computers.
(The fact that the input has to be finite is just a reflection that we care about problems that can be solved in finite time, and it’s not feasible to feed an infinite amount of data into a computer in a finite time, or even to store an infinite amount of data in a physical computer.)
The second assumption, that we only care about the output is a single boolean, is perhaps more debatable. The idea is that any “real” computation can be described as a sequence of decision problems.
For example, if we wanted to compute 3×7, we could answer this by
solving a sequence of decision problems: - Is "3x7=0"
correct? - Is "3x7=1" correct? - Is "3x7=2"
correct? - Is "3x7=3" correct? - etc.
until we get a positive answer and discover that 3×7 is 21.
Conversely, if a computer can calculate some arbitrary answer to a computation, it should be able to answer simple yes-no questions about that answer.
Example
More generally, any computation of an answer could be reduced to
questions like: >- Does the output (as a binary sequence) have length
"0"? >- Does the output (as a binary sequence) have
length "1"? >- Does the output (as a binary sequence)
have length "2"? >- etc. > > or >- Is the bit
at offset "0" of the output (as a binary sequence) equal to
1? >- Is the bit at offset "1" of the output (as a
binary sequence) equal to 1? >- Is the bit at offset "2"
of the output (as a binary sequence) equal to 1? >- etc.
Example
What does it mean for something like a video game to be computable?
Well, we could reconstruct the entire play of a game by answering an incredibly long (but finite!) sequence of decision problems such as > > if the time is [specify a time or frame number] and the user’s actions so far have been [all the key presses, joystick motions, etc., and when they happened], will the redness of the pixel at [specify x,y coordinates on the screen] be equal to [specify a value]? > >(If the game involves “randomness”, then the premises of our question might need to include not just what the user did, but also internal game actions like the finite list of all random numbers the computer had generated to that point.)
If we put the two assumptions together, we only care about decision problems where the input is a finite string. There is a very nice mathematical characterization of such problems: we can describe any computational problem as answering the question “Is the input a member of the set \(L\) ?” for a suitable set \(L\) of finite strings!
Example
\[ \{\mathtt{"in"}, \mathtt{"by"}, \mathtt{"with"}, \ldots\} \] - The decision problem “Is the input string is a number that is a multiple of 3?” is equivalent to asking whether the input is a member of the infinite set of strings \[\{\mathtt{"0"}, \mathtt{"3"}, \mathtt{"6"}, \ldots\}\] - The decision problem “Is the input string a palindrome?” is equivalent to asking whether the input is a member of the infinite set of strings \[\{\mathtt{""}, \mathtt{"a"}, \mathtt{"aa"}, \ldots \mathtt{"kayak"}, \ldots, \mathtt{"racecar"}, \ldots, \mathtt{"deified"}, \ldots\} \] - The decision problem “Is the input string a correct multiplication?” is equivalent to asking whether the input is a member of the infinite set of strings
\[ \{\mathtt{"0×0=1"}, \mathtt{"0×1=1"}, \ldots, \mathtt{"23×17=391"}, \ldots\} \]
Definition
We say that a set of strings \(L\) is decidable if a computer can return “true” when given a string that is a member of \(L\) and return “false” when given a string that is not a member of \(L\).
Warning: We are not saying the computer needs to do this by constructing the set in memory and then doing a set-lookup operations!
For example, if we can write a function (in Python, say) that takes a string input and then returns whether that string is the same forward and backward, this prove that a computer can decide whether a string is a palindrome or not, and we can conclude that “the set of all palindromes” is decidable.
Example
A typical computation we might be interested in is computing the \(n^\mathrm{th}\) prime number for any given \(n\). > One way to demonstrate this is possible is to show that a computer can answer the decision problem, “is the given number prime?”. (By checking the primality of enough numbers, we can eventually find the \(n^\mathrm{th}\) prime number.) > Saying that a computer program can answer the question “is the given number prime?” is equivalent to saying that “the set of all prime numbers is a decidable set.”
At this point, we have reduced the very vague question of “what problems can we solve using computers” to the much more precise question, “Which sets of strings are decidable using a computer?”
To answer that, we need to formally define what counts as a computer. There are many reasonable definitions, each with strengths and weaknesses. In this class we will mostly focus on two very broad definitions of Computer (finite state machines and Turing machines), though other models of computation will be mentioned along the way.
Before we try to formally define what counts as a computer, though, we will introduce notation that makes working with strings and sets of strings a bit simpler.
Previous: 5.3 Uncountable Sets
Next: 6.2 String Theory